/*
*       版权归 仓库所有者cc01cc(cc01cc@foxmail.com) 所有
*       此文件内的源码在遵循以下条例的前提下，提供自由使用：
*       一. 未经 仓库所有者cc01cc(cc01cc@foxmail.com) 书面许可:
*           1. 任何企业单位组织严禁将源码直接用于商业以及一切涉及获利的行为。
*       二. 未经 仓库所有者cc01cc(cc01cc@foxmail.com) 许可:
*           1. 任何企业单位组织严禁将源码以任何形式用于商业以及一些涉及获利的行为。
*           2. 任何个人严禁将源码以任何形式用于商业以及一些涉及获利的行为。
*       三. 申明:
*           1. 源码作者保留所有专利权，并开放专利使用权。
*           2. 若使用源码造成任何形式的损失，源码作者不承担任何责任。
*           3. 若由于使用源码造成任何形式的损失，由使用者提供全部赔偿。
*       四. 除上述之外，所有未定义事项遵循 AGPL-3.0 许可协议
*/

/*
 *     Copyright (c) 2021. cc01cc(cc01cc@foxmail.com). All rights reserved.
 *
 *     This is part of this file.
 *
 *     This file is free software: you can redistribute it and/or modify
 *     it under the terms of the GNU Affero General Public License as published
 *     by the Free Software Foundation, either version 3 of the License, or
 *     (at your option) any later version.
 *
 *     This file is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU Affero General Public License for more details.
 *
 *     You should have received a copy of the GNU Affero General Public License
 *     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#include <stdio.h>
#include <stdlib.h>

struct Peanut
{
//  前缀 i 表示位置或者索引，例如数组的下标
    int i_row;
    int i_column;
//  前缀 n 表示事物的总数
//  例如 n_peanut 表示花生的总数
    int n_peanut;
//  前往植株所需的总时间（包括采摘花生的时间）
    int n_time_go;
//  通常来讲，变量命名范围从小到大，如：n_go_time
//  但是为了区分 'time' 和 'peanut' 此处使用，n_time_go
//  从该植株返回所需的总时间
    int n_time_back;
};

typedef struct Peanut Peanut;

int storeData(int row, int column, Peanut* p_peanut);
void sortLargeToSmall(Peanut* p_peanut, int limit);
void peanutInitial(Peanut* p_peanut);
int countPeanutPicked(Peanut* p_peanut, int limit, int n_plant_have_peanut);
int main()
{
    int row, column;
    int n_time_limit;
    int n_plant_have_peanut;
    int n_peanut_picked;
    Peanut peanut[1000];

    freopen("data.txt","r",stdin);

    scanf("%d%d%d", &row, &column, &n_time_limit);
    n_plant_have_peanut = storeData(row, column, peanut);
    //  如果没有植株拥有花生就直接返回 0
    if(n_plant_have_peanut==0)
    {
        printf("The number of peanut is 0.");
        return 0;
    }
    sortLargeToSmall(peanut, n_plant_have_peanut);
    peanutInitial(peanut);
    n_peanut_picked = countPeanutPicked(peanut, n_time_limit, n_plant_have_peanut);
    printf("The number of peanut is %d.", n_peanut_picked);
}

//********************************************************************************
//  返回：拥有花生的植株的总数
//  功能：读取并存储拥有花生的植株的位置，花生数量，以及返回时间
//********************************************************************************
int storeData(int row, int column, Peanut* p_peanut)
{
    int i,j,data;
    int i_peanut = 0;
    // i_peanut 表示 p_peanut 的索引，
    // 根据语义化的要求，不宜用于表示植株总数，
    // 并防止与 n_peanut 混淆，故定义 n_plant
    int n_plant = 0;
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < column; j++)
        {
            scanf("%d", &data);
            if(data!=0)
            {
                n_plant++;
                p_peanut[i_peanut].i_row = i+1;
                p_peanut[i_peanut].i_column = j+1;
                p_peanut[i_peanut].n_time_back = i+1;
                p_peanut[i_peanut].n_peanut = data;
                i_peanut++;
            }
        }
    }
    return n_plant;
}

//****************************************************************************
//  作用：使用插入排序，将 p_peanut 数组以 p_peanut.n_peanut 的值从大到小排序
//****************************************************************************
void sortLargeToSmall(Peanut* p_peanut, int limit)
{
    int i, j,x;

    Peanut p_tmp;
    for(i = 1; i < limit; i++)
    {
        p_tmp = p_peanut[i];
        for(j = i; j > 0 && p_peanut[j - 1].n_peanut < p_tmp.n_peanut; j--)
        {
            p_peanut[j] = p_peanut[j - 1];
        }
        p_peanut[j] = p_tmp;
    }
}

//***********************************************************************
//  !注意：此函数必须确保 p_peanut[0].i_row 存在有效值
//  作用：计算 前往以及采摘第一份植株 p_peanut[0] 所需的时间
//***********************************************************************
void peanutInitial(Peanut* p_peanut)
{
    p_peanut[0].n_time_go = p_peanut[0].i_row+1;
}

//*******************************************
//  作用：计算采摘花生的总数
//*******************************************
int countPeanutPicked(Peanut* p_peanut, int limit, int n_plant_have_peanut)
{
    int i = 0;
    int n_peanut_picked = 0;
    while(i<n_plant_have_peanut&&p_peanut[i].n_time_go+p_peanut[i].n_time_back<=limit)
    {
        n_peanut_picked += p_peanut[i].n_peanut;
        i++;
        p_peanut[i].n_time_go = abs(p_peanut[i].i_column-p_peanut[i-1].i_column)
        + abs(p_peanut[i].i_row-p_peanut[i-1].i_row)
        + p_peanut[i-1].n_time_go + 1;
    }
    return n_peanut_picked;
}
